#lang racket
(provide travers)

;; Expr Syntax [Listof Bindings]-> [BindList Syntax]
;; finds all bound variable in syntax given its quoted list form.
;; Invar: if stx was passed in as #'sty then exp was passed in as (syntax->datum #'sty)
(define (travers exp stx [locals empty])
  (cond [(empty? exp) null]
        [(binding-e? exp)
         (list (list 'list `(quote ,exp) (if (assoc exp locals) `(quote ,(cadr (assoc exp locals))) stx)))]
        [(let-e? exp)
         (travers (third exp) (car-syntax (cdr-syntax (cdr-syntax stx)))
                  (append (cadr exp) locals))]
        [(trav-e? exp)
         (append (travers (car exp) (car-syntax stx) locals)
                 (travers (cdr exp) (cdr-syntax stx) locals))]
        [else null]))

;; Syntax -> Syntax
;; gets the first element of syntax->list
(define (car-syntax stx)
  (car (syntax->list stx)))

;; Syntax -> Syntax
;; gets the 'rest' of a syntax by rebuilding syntax->list
(define (cdr-syntax stx)
  (datum->syntax stx (cdr (syntax->list stx))))

;; Expr -> Any
;; is this a binding?
(define (binding-e? exp)
  (and (symbol? exp)
       (not (or (symbol=? exp 'if)
                (symbol=? exp 'quote)
                (let? exp)
                (symbol=? exp 'define)))))

;; Expr -> Any
;; is this an expression that the first an rest are traversable?
(define (trav-e? exp)
  (and (cons? exp)
       (not (and (symbol? (car exp))
                 (or (let? (car exp))
                     (symbol=? (car exp) 'λ)
                     (symbol=? (car exp) 'lambda)
                     (equal? 'quote (car exp)))))))
;; Symbol -> Any
;; is this a let symbol?
(define (let? s)
  (or (symbol=? s 'let)
      (symbol=? s 'let*)
      (symbol=? s 'letrec)))

;; Expr -> Any
;; is this a let expression?
(define (let-e? exp)
  (and (cons? exp)
       (symbol? (car exp))
       (let? (car exp))))